package com.leetcode.algs4.sort;

/**
 * @author Dennis Li
 * @date 2020/6/14 21:27
 */
public class HeapSort {

    public static void sort1(int[] arr) {
        int N = arr.length - 1;
        // 建堆的模式是自下而上进行的，完全二叉树的性质，数组从1开始记录
        for (int i = N / 2; i >= 1; i--) {
            // 下沉建堆。保证父节点比两个子节点大
            sink(arr, i, N);
        }
        while (N > 1) {
            // 将最大的值交换到最后面（删除最大元素），并且数组长度减一。这样下去可以得到最终有序的数组
            swap(arr, 1, N--);
            // 原堆被打破，从子节点选择一个最大的替换堆顶。对交换后的堆进行下沉再排序
            sink(arr, 1, N);
        }
    }

    private static void sink1(int[] arr, int a, int N) {
        // 需要从上至下进行遍历
        while (2 * a <= N) {
            // 子节点坐标
            int j = a * 2;
            // 右子节点比左子节点大，选择右子节点， 并且坐标要保证不超过N
            if (j < N && arr[j + 1] > arr[j]) j++;
            // 如果父堆比子堆大，则不需要下沉。因为默认是从下自上建堆的
            if (arr[a] > arr[j]) break;
            // arr[a] < arr[j] 交换a和j的位置，因为j的序号较大，需要将较大值放到后面
            swap(arr, a, j);
            // 继续遍历子节点
            a = j;
        }
    }

    public static void sort(int[] arr) {
        int N = arr.length - 1;
        for (int i = N / 2; i >= 1; i--) {
            sink(arr, 1, N);
        }
        while (N >= 1) {
            swap(arr, 1, N--);
            sink(arr, 1, N);
        }
    }

    private static void sink(int[] arr, int a, int N) {
        while (a * 2 < N) {
            int j = a * 2;
            if (j < N && arr[j] < arr[j + 1]) j++;
            if (arr[j] < arr[a]) break;
            swap(arr, j, a);
            a = j;
        }
    }


    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
